21/05/2007

Problème P = NP ?

Proposé par : Gilbert Han et Benjamin Cohen Solal

Tout d'abord, voici un lien vers la version Word 2007 (.docx) et la version PDF de ce rapport (nettement plus lisible) : http://www.box.net/shared/mtj9g5m6yx

Table des matières

Introduction

Quelques concepts

Complexité

Déterminisme et non déterminisme

Algorithmes polynômiaux

La classe P

La classe NP

Le problème P = NP

Conclusion

 

Introduction

Un champ de recherche majeur des mathématiques actuelles est l'investigation de la propriété : a-t-on P=NP ? Autrement dit, peut-on trouver en temps polynômial ce que l'on peut prouver en temps polynômial ? Ce problème est si important qu'il fait partie des 7 problèmes du millénaire, dont la résolution est primée 1 million de dollars par le Clay Mathematic Institute.

Une autre formulation est : « Tout ce que l'on peut vérifier facilement, peut-il être découvert aisément ? ». Vérifier qu’un chemin dans un graphe passe par tous les nœuds du graphe sans jamais passer deux fois par le même nœud (chemin hamiltonien) est facile, trouver le chemin n’est pas facile (aujourd'hui, aucun algorithme efficace ne le permet).

Quelques concepts

Complexité

La complexité algorithmique est un moyen d'évaluation du coût d'un algorithme. Cette complexité mesure le nombre d'opérations élémentaires et le coût mémoire. Cela permet surtout de connaitre le type de croissance en fonction de la taille des données. La complexité d’un problème est l’ordre de grandeur de la complexité (dans le pire cas) du meilleur algorithme connu pour le résoudre. La théorie de la complexité algorithmique s'intéresse à l'estimation de l'efficacité des algorithmes. Elle s'attache à la question : entre différents algorithmes réalisant une même tâche, quel est le plus rapide et dans quelles conditions ?

Déterminisme et non déterminisme

Une machine déterministe est le modèle formel d'une machine telle que nous les connaissons (nos ordinateurs sont des machines déterministes). Les deux modèles les plus utilisés en informatique théorique sont :

• La machine de Turing

• La machine RAM (Random access machine)

Les machines déterministes font toujours un seul calcul à la fois. Ce calcul est constitué d'étapes élémentaires. A chacune de ces étapes, pour un état donné de la mémoire de la machine, l'action élémentaire effectuée sera toujours la même. Pour la suite, on pourra imaginer sans perte de généralité qu'une machine de Turing déterministe correspond à l'ordinateur favori du lecteur, programmé dans un langage impératif quelconque.

Une machine de Turing non-déterministe est une variante purement théorique des machines de Turing: on ne peut pas construire de telle machine. À chaque étape de son calcul, cette machine peut effectuer un choix non-déterministe: elle a le choix entre plusieurs actions, et elle en effectue une. Si l'un des choix l'amène à accepter l'entrée, on considère qu'elle a fait ce choix-là. En quelque sorte, elle devine toujours juste. Une autre manière de voir leur fonctionnement est de considérer qu'à chaque choix non-déterministe, elles se dédoublent, les clones poursuivent le calcul en parallèle suivant les branches du choix. Si l'un des clones accepte l'entrée, on dit que la machine accepte l'entrée.

Il semblerait donc naturel de penser que les machines de Turing non-déterministes sont beaucoup plus puissantes que les machines de Turing déterministes, autrement dit qu'elles peuvent résoudre en un temps raisonnable des problèmes que les machines ordinaires ne savent pas résoudre à moins de prendre des années.

Algorithmes polynômiaux

Un algorithme est dit en temps polynômial si, pour tout n, pour des données ne prenant pas plus de n octets, l'algorithme s'exécute en moins de C × nk opérations élémentaires (les constantes C et k étant bien sûr indépendantes de n).

Dans la définition précédente, le terme d'opérations élémentaires est assez vague. On doit le comprendre comme des additions, des multiplications, des comparaisons, etc. (tout ce que le processeur sait réaliser en un temps fixe). Ce qu'il faut retenir, c'est que les algorithmes polynômiaux sont les seuls à pouvoir être utilisés informatiquement pour de grandes valeurs de n, et ce, quelle que soit la puissance de la machine.

La classe P

Un problème de décision est dans P s'il peut être décidé par un algorithme déterministe en un temps polynomial par rapport à la taille de l'instance. On qualifie alors le problème de polynomial.

Prenons par exemple le problème de la connexité dans un graphe. Étant donné un graphe à s sommets, il s'agit de savoir si toutes les paires de sommets sont reliées par un chemin. Pour le résoudre, on dispose de l'algorithme de parcours en profondeur qui va construire un arbre couvrant du graphe à partir d'un sommet. Si cet arbre contient tous les sommets du graphe, alors le graphe est connexe. Le temps nécessaire pour construire cet arbre est au plus s2, donc le problème est bien dans la classe P.

Les problèmes dans P correspondent en fait à tous les problèmes facilement solubles.

La classe NP

La définition d'un problème NP peut sembler complexe. Essayons de l'éclaircir. Un des problèmes difficiles des mathématiques est la factorisation d'un entier en produit de facteurs premiers. On ne sait pas s'il existe un algorithme polynômial qui réussisse cette opération. Autrement dit, on ne sait pas si ce problème est dans P. En revanche, étant donné des nombres p1, …, pk, il est trivial de vérifier si n = p1…pk : ce problème est dans NP.

Pour résumer, être dans P, c'est trouver une solution en temps polynômial, tandis qu'être dans NP, c'est prouver en temps polynômial qu'une proposition de réponse est une solution du problème. Ainsi, tout problème qui est dans P se trouve dans NP.

Le problème P = NP

Le problème P = NP revient à savoir si on peut résoudre un problème NP-Complet avec un algorithme polynomial. Les problèmes étant tous classés les uns à partir des autres (un problème est NP-Complet si l'on peut réduire un problème NP-Complet connu en ce problème), faire tomber un seul de ces problèmes dans la classe P fait tomber l'ensemble de la classe NP, ces problèmes étant massivement utilisés, en raison de leur difficulté, par l'industrie, notamment en cryptographie (la factorisation en nombres premiers). Ceci fait qu'on conjecture cependant que les problèmes NP-complets ne sont pas solubles en un temps polynomial.

À partir de là plusieurs approches sont tentées :

• Des algorithmes d'approximation permettent de trouver des solutions approchées de l'optimum en un temps raisonnable pour un certain nombre de programmes. Dans le cas d'un problème d'optimisation on trouve généralement une réponse correcte, sans savoir s'il s'agit de la meilleure solution ;

• Des algorithmes stochastiques : en utilisant des nombres aléatoires on peut « forcer » un algorithme à ne pas utiliser les cas les moins favorables, l'utilisateur devant préciser une probabilité maximale admise que l'algorithme fournisse un résultat erroné. Citons notamment comme application des algorithmes de test de primalité en temps polynomial en la taille du nombre à tester. A noter qu'un algorithme polynomial non stochastique a été proposé pour ce problème en août 2002 par Agrawal, Kayal et Saxena ;

• Des heuristiques permettent d'obtenir des solutions généralement bonnes mais non exactes en un temps de calcul modéré ;

• Des algorithmes par séparation et évaluation permettent de trouver la ou les solutions exactes. Le temps de calcul n'est bien sûr pas borné « polynomialement » mais, pour certaines classes de problèmes, il peut rester modéré pour des instances relativement grandes ;

• On peut restreindre la classe des problèmes d'entrée à une sous-classe suffisante, mais plus facile à résoudre.

Si ces approches échouent, le problème est non soluble en pratique dans l'état actuel des connaissances.

Conclusion

La question « P = NP ? » est l'un de sept problèmes sélectionnés par l'Institut Clay en l'an 2000 : comme pour les six autres, une somme d'un million de dollars attend celle, celui ou ceux qui le résoudront. Certains affirment que c'est le plus important des sept problèmes et donc la principale énigme des mathématiques d’aujourd'hui. Il semble aussi être le seul dont la résolution aurait des conséquences pratiques (il est lié à des centaines d’énoncés concrets) et sa portée philosophique est la plus grande : la question « P = NP ? » concerne la nature de la recherche de solution(s) dans un ensemble exponentiel de possibilités, ce qui est le problème même de la recherche scientifique.

En revanche, la résolution de ce problème peut également avoir un impact négatif sur l’informatique, notamment en cryptographie où beaucoup d’algorithmes de cryptage deviendraient facilement « crackable » et par conséquent inutiles.